class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int carry = 0;
        int n = a.length();
        int m = b.length();
        int i = n - 1;
        int j = m - 1;
        string ans;

        while (i >= 0 || j >= 0 || carry) {
            if (i >= 0) {
                carry += a[i] - '0';
            }
            if (j >= 0) {
                carry += b[j] - '0';
            }
            ans += static_cast<char>(carry % 2 + '0');
            carry /= 2;
            --i;
            --j;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
